package algorithm.kmp;

/**
 * @program: util
 * @description: kmp算法，字符串匹配
 * @author: zhouliangliang
 * @create: 2019-07-23 17:16
 **/
public class Kmp {

    /**
     * 利用next数组求解
     * @param str
     * @param pStr
     * @return
     */
    public int kmp(String str, String pStr) {
//        System.out.println(str.length());
//        System.out.println(pStr.length());
        int j = 0;
        int next [] = this.next(pStr, pStr.length());
        for(int i=0; i<str.length(); i++) {
            while(j >0 && str.charAt(i) != pStr.charAt(j)) {
                j = next[j-1];
            }

            if(str.charAt(i) == pStr.charAt(j)) {
                j++;
            }

            if(j == pStr.length()) {
                return i - j + 1;
            }
        }

        return -1;
    }

    /**
     * 求next数组
     * 前缀和后缀公共部分的最大长度的集合
     * @param pStr
     * @param length
     */
    public int[] next(String pStr, int length) {
        int next[] = new int[length];
        next[0] = 0;
        int k = 0;
        for(int i=1; i<pStr.length(); i++) {
            if(k >0 && pStr.charAt(k) != pStr.charAt(i)) {
                k = next[k-1];
            }

            if(pStr.charAt(k) == pStr.charAt(i)) {
                k++;
            }

            next[i] = k;
        }
        return next;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        for(int i=0; i<100000000; i++) {
//            String pStr = "%E5%8C%97%E4%BA%AC";
//            String str = "http://10.24.134.56:8080/monitor/api?facadeKey=gaode-test&serviceType=geo&thirdParty=gaode&address=%E5%8C%97%E4%BA%AC";
            String pStr = "中国";
            String str = "我爱你中国哈哈!";

            int index = new Kmp().kmp(str, pStr);
            System.out.println(index);
//            System.out.println(str.substring(index, index + pStr.length()));
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start);

    }
}
//23343
